import java.util.Arrays;

public class MyHeap {
    public int[] elem;
    public int usedSize;

    public MyHeap(){
        this.elem = new int[10];
    }

    public void initElem(int[] arr){
        for(int i = 0; i < arr.length; i++){
            elem[i] = arr[i];
            usedSize++;
        }
    }

    /*
    创建大根堆
     */
    public void createHeap(){
        for(int parent = (usedSize - 1 - 1) / 2 ; parent >= 0; parent--){
            shiftDown( parent, usedSize);
        }
    }

    private void shiftDown(int parent , int len){
        // 至少有左孩子
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < len && elem[child] < elem[child + 1]){
                child++;
            }

            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    // 堆的插入，要借助向上调整
    public void insert(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem, elem.length + 5);
        }

        elem[usedSize++] = val;
        shiftUp(usedSize - 1);
    }

    private boolean isFull(){
        return usedSize == elem.length;
    }

    private void shiftUp(int child){
        int parent = (child - 1) / 2;
        while(child > 0){
            if (elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }

    // 堆的删除
    public void pop(){
        if (isEmpty()){
            return;
        }

        elem[0] = elem[usedSize - 1];
        usedSize--;

        shiftDown(0, usedSize);
    }

    private boolean isEmpty(){
        return usedSize == 0;
    }

    // 堆排序
    private void  swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void sort(){
        int end = usedSize - 1;
        while(end > 0){
            swap(elem, 0, end);
            shiftDown(0, end);
            end--;
        }
    }



}
